/*
 * @Author: szx
 * @Date: 2022-03-20 14:24:57
 * @LastEditTime: 2022-03-20 15:10:22
 * @Description:
 * @FilePath: \leetcode\2000-2099\2039\2039.js
 */
/**
 * @param {number[][]} edges
 * @param {number[]} patience
 * @return {number}
 */
var networkBecomesIdle = function (edges, patience) {
    // 创建graph图
    const n = patience.length,
        graph = new Array(n).fill(0).map(() => []);
    for (let edge of edges) {
        graph[edge[0]].push(edge[1]);
        graph[edge[1]].push(edge[0]);
    }

    // bfs来获得每条路线最短的路径
    let cnt = 0;
    let queue = [0];
    const distance = new Array(n).fill(Number.MAX_SAFE_INTEGER);
    while (queue.length) {
        const next = [];
        cnt++;
        for (let i of queue) {
            for (let j of graph[i]) {
                if (distance[j] === Number.MAX_SAFE_INTEGER) {
                    distance[j] = cnt;
                    next.push(j);
                }
            }
        }
        queue = next;
    }
    let res = 0,
        max = 0;
    for (let i = 1; i < n; i++) {
        const len = distance[i] * 2;
        max = Math.floor((len - 1) / patience[i]) * patience[i] + len;
        res = Math.max(res, max);
    }
    return res + 1;
};
console.log(
    networkBecomesIdle(
        [
            [0, 1],
            [1, 2]
        ],
        [0, 2, 1]
    )
);

console.log(
    networkBecomesIdle(
        [
            [0, 1],
            [0, 2],
            [1, 2]
        ],
        [0, 3, 10]
    )
);
